using System.Collections.Generic;
using UnityEngine;

public class QuadTree
{
    //下文两个大写字母的变量可变成静态/常量，按需更改
    //节点内允许的最大对象
    private readonly int MAX_OBJECTS = 1;
    //最大层级
    private readonly int MAX_LEVELS = 3;
    //当前层级
    private readonly int level;
    //当前层级内的对象
    public List<RectTransform> rectTrans;
    //rect范围
    private Rect bounds;
    //子节点
    private readonly List<QuadTree> childs;
    /// <summary>
    /// 构造函数
    /// </summary>
    public QuadTree(Rect pBounds, int pLevel = 0, int maxObjs = 1, int maxLevel = 3)
    {
        rectTrans = new List<RectTransform>();
        childs = new List<QuadTree>();
        bounds = pBounds;
        level = pLevel;
        MAX_OBJECTS = maxObjs;
        MAX_LEVELS = maxLevel;
    }
    
    /// <summary>
    /// 清理四叉树，包括他包含的物体与所有子结点
    /// </summary>
    public void Clear()
    {
        //清理包含的物体
        rectTrans.Clear();
        //子结点将递归清理
        for (int i = 0; i < childs.Count; i++) childs[i].Clear();
    }
    
    /// <summary>
    /// 获取对象的rect
    /// </summary>
    /// <param name="rectTransform">RectTransform</param>
    /// <returns>对象的rect</returns>
    public Rect GetRect(RectTransform rectTransform)
    {
        Rect rect = rectTransform.rect;
        return new Rect(rectTransform.position.x + rect.x, rectTransform.position.y + rect.y, rect.width, rect.height);
    }
    
    /// <summary>
    /// 查找rect所在的最小树结点有哪些，并通过List的引用进行添加
    /// </summary>
    /// <param name="rect">要查找的对象</param>
    /// <param name="quadTrees">返回列表</param>
    public void FindQuad(Rect rect, List<QuadTree> quadTrees)
    {
        //如果当前这个树的范围包括了rect
        if (bounds.Overlaps(rect))
        {
            //如果当前结点已经没有子结点，一定是最小结点
            if (childs.Count == 0) quadTrees.Add(this);
            else
            {
                //否则一直向子结点找下去
                for (int i = 0; i < childs.Count; i++) childs[i].FindQuad(rect, quadTrees);
            }
        }
    }
    /// <summary>
    /// 获取到有哪些最小树结点包含了参数这个对象
    /// </summary>
    /// <param name="rect">对象的rect</param>
    /// <returns>包含对象的树节点列表</returns>
    public List<QuadTree> GetIndexes(Rect rect)
    {
        List<QuadTree> ret = new();
        //进行查找并且直接返回
        FindQuad(rect, ret);
        return ret;
    }
    
    
    /// <summary>
    /// 插入一个新的Rect
    /// </summary>
    public void Insert(RectTransform go)
    {
        //获取到这个物体的Rect
        Rect rect = GetRect(go);
        //获取到有哪些最小树结点包括了这个物体，由于物体可能脚跨多个区域，所以返回的是List
        List<QuadTree> tempList = GetIndexes(rect);
        //遍历包括这个物体的最小树结点
        for (int i = 0; i < tempList.Count; i++)
        {
            QuadTree quad = tempList[i];
            //为这个结点的物体List加入go
            quad.rectTrans.Add(go);
            //如果这个结点存储的物体数量超过了自己应该存的最大物体数量，并且还没有分割到超过最大树层级，那么需要对这个结点进行分割
            if (quad.rectTrans.Count > MAX_OBJECTS && quad.level < MAX_LEVELS)
            {
                quad.Split();
            }
        }
    }
    
    /// <summary>
    /// 分割四叉树，为这个结点计算出四个子结点
    /// </summary>
    public void Split()
    {
        //这部分是计算子结点的x,y,w,h
        float halfWidth = bounds.width / 2;
        float halfHeight = bounds.height / 2;
        float x = bounds.x;
        float y = bounds.y;
        childs.Add(new QuadTree(new Rect(x, y + halfHeight, halfWidth, halfHeight), level + 1, MAX_OBJECTS, MAX_LEVELS));
        childs.Add(new QuadTree(new Rect(x + halfWidth, y + halfHeight, halfWidth, halfHeight), level + 1, MAX_OBJECTS, MAX_LEVELS));
        childs.Add(new QuadTree(new Rect(x, y, halfWidth, halfHeight), level + 1, MAX_OBJECTS, MAX_LEVELS));
        childs.Add(new QuadTree(new Rect(x + halfWidth, y, halfWidth, halfHeight), level + 1, MAX_OBJECTS, MAX_LEVELS));
        //遍历自己的物体List，然后将这些物体全部进行下沉到子结点
        for (int i = 0; i < rectTrans.Count; i++)
        {
            Insert(rectTrans[i]);
        }
        //由于四叉树算法的思想是物体全部由最小子结点保存并计算，当一个结点被分割后，就代表他不是最小子结点了，需要清除他保存的物体
        rectTrans.Clear();
    }
    
    
    /// <summary>
    /// 获取所有有意义（包含物体的）叶子结点（叶子结点指的是最子层的结点）
    /// </summary>
    /// <param name="ret">用于out的列表</param>
    public void GetAllLeaf(List<QuadTree> ret)
    {
        //如果没有子结点，说明已经是最小结点，要是包含物体，加入自身
        if (childs.Count == 0)
        {
            if (rectTrans.Count > 1)
                ret.Add(this);
        }
        else
        {
            //否则对自己的子结点进行递归
            for (int i = 0; i < childs.Count; i++) childs[i].GetAllLeaf(ret);
        }
    }
    
    /// <summary>
    /// 获取所有相交的对象
    /// </summary>
    public Dictionary<RectTransform, HashSet<RectTransform>> GetAllCollisions()
    {
        //ret是返回值，这个字典的Key是一个物体，他的Value是这个物体检测范围内的其他物体的集合，存在Key的条件是这个物体至少与其他一个物体在检测范围内
        Dictionary<RectTransform, HashSet<RectTransform>> ret = new();
        List<QuadTree> leafs = new();
        //获取全部包含物体的最小子结点
        GetAllLeaf(leafs);
        //遍历全部上述最小结点
        for (int i = 0; i < leafs.Count; i++)
        {
            //遍历目前这个最小结点的全部物体
            for (int j = 0; j < leafs[i].rectTrans.Count; j++)
            {
                //二层遍历，我只需要比较这个结点内的几个物体互相有没有在范围检测内
                for (int k = j + 1; k < leafs[i].rectTrans.Count; k++)
                {
                    //如果ret包含现在遍历到的这个物体，并且已经存过了要检测的物体，继续；反之亦然
                    if (ret.ContainsKey(leafs[i].rectTrans[j]) && ret[leafs[i].rectTrans[j]].Contains(leafs[i].rectTrans[k])) continue;
                    if (ret.ContainsKey(leafs[i].rectTrans[k]) && ret[leafs[i].rectTrans[k]].Contains(leafs[i].rectTrans[j])) continue;
                    //没有继续，进行一次范围检测
                    Rect rect1 = GetRect(leafs[i].rectTrans[j]);
                    Rect rect2 = GetRect(leafs[i].rectTrans[k]);
                    //如果rect1与rect2范围相交
                    if (rect1.Overlaps(rect2))
                    {
                        //如果rect1还没有被添加，先初始化一个，防止没有Key或者空Value
                        if (!ret.ContainsKey(leafs[i].rectTrans[j])) ret.Add(leafs[i].rectTrans[j], new HashSet<RectTransform>());
                        //为这个物体的检测集合添加rect2的物体
                        ret[leafs[i].rectTrans[j]].Add(leafs[i].rectTrans[k]);
                    }
                }
            }
        }
        return ret;
    }
}
